package com.dyz.leetcode._06_binarySearch;

public class _1539_findKthPositive {
    public int findKthPositive1(int[] arr, int k) {
        int currNum = 1;
        int lastNum = -1;
        int missCount = 0;
        int i = 0;
        while(missCount<k){
            if(currNum==arr[i]){
                i = (i+1<arr.length)?i+1:i;
            }else{
                missCount++;
                lastNum = currNum;
            }
            currNum++;
        }
        return lastNum;
    }
    public int findKthPositive(int[] arr, int k) {
        if (arr[0] > k) {return k;}
        /*
        解释：right 为什么是 arr.length 而非 arr.length - 1
        因为这里你需要考虑缺失的数字可能是数组最后一个元素的下一个整数，
        所以，这里进行二分的时候，范围必须是 [0....nums.length] 中查找
        比如：[1, 2, 3, 4, 5]  k = 1，
        那么这个时候第 1 个缺失的数字是 6 ，是数组最后一个元素的下一个整数

        就是说你要查找的数字有可能超出数组的范围
         */
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] - mid - 1 < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // left
        int leftMissCnt = arr[left - 1] - (left - 1) - 1;
        return arr[left - 1] + (k - leftMissCnt);
    }
}
